Virtual machines are software implementations of a physical device that can run programs analogous to a physical device. Virtual machines provide various benefits, but are not without their problems. One such problem is that it can be desirable to backup the data and state of a virtual machine, but such backups can be time consuming and require large amounts of storage space due to the amount of information (the data and state of the virtual machine) being backed up. Additionally, such backups can be difficult to implement due to the ability of many virtual machines to be migrated or moved to different physical host devices, and/or the ability for the underlying physical storage devices used by virtual machines to be changed.